1. Field of the Invention
The present invention relates to a tally image generating method, a decoding method, a tally image generator, and a decoder, and in particular, to a tally image generating method, a decoding method, a tally image generator, and a decoder which can generate high-quality tally images and decode a confidential image with a high resolution.
2. Description of the Related Art
Conventionally, tally image generating methods using the halftone technique have been proposed. “Tally” means that, although one or a partial tally does not show confidential information, the confidential information is known by superposing a plurality of tallies.
In Non-Patent Document 1, a tally image generating method using an error diffusion method is described. According to this method, errors are diffused to high-frequency components by a weighting filter, so that tally images with high quality can be generated.
In Non-Patent Document 2, a tally image generating method using a genetic algorithm (GA) is described. In this method, tallies are generated so that density values calculated by applying a Gaussian filter to a generated binary image become close to input pixel values of a gray-scale image, so that high-quality tally images can be generated.
In Non-Patent Document 3, a tally image generating method using a systematic ordered dither method is described. This is a method for generating tally images with a size equal to the size of an input gray-scale natural image in the same manner as in Non-Patent Document 1 and Non-Patent Document 2, and two threshold matrices like Bayer's matrix (the matrix size is normally 4×4) are used by being randomly switched for each pixel of a confidential image, and values of a threshold matrix are compared with the each pixel of the input gray-scale image, whereby tally images are generated at a high speed.
FIG. 1 shows an example of matrix switching in a tally image generating method using a systematic ordered dither method.
In Patent document 1, a tally image generating method using a density pattern method is described. This is a method for expressing a pixel value of an input gray-scale image by densities of d×d binary pixels (d is normally 2 through 4) of a tally image. The amount of calculation is small.
By using tally images generated by the tally image generating methods as described above, confidential information can be visually decoded without using a calculator. For example, tally images are printed on transparent sheets, and the transparent sheets are overlapped each other, whereby confidential information can be decoded.
[Patent Document 1] Japanese Patent Laid-open H09-252397
[Patent document 2] Japanese Patent Laid-open 2003-198526
[Patent document 3] Japanese Patent Laid-open 2002-358013
[Non-Patent Document 1] M. S. Fu, O. C. Au, “Data Hiding in Halftone Images using Stochastic Error Diffusion,” Proc. of IEEE Int. Conf. on Acoustics, Speech, and Signal Processing, Vol. 3, pp. 1965-1968, 2001
[Non-Patent Document 2] Emi Myodo and Kiyoshi Tanaka, “A Watermark Sharing Scheme to High Quality Halftone Images with Genetic Algorithms,” Applications of Evolutionary Computing: EvoWorkshops 2004, LNCS, Springer, Vol. 3005, pp. 339-348, 2004.
[Non-Patent Document 3] Kazuhiro Oka and Kineo Matsui, “Embedding of Signed Information in Hardcopy Images by Systematic Dither Method,” IEICE Trans. Fundamentals, Vol. J80-D-II, No. 3, pp. 820-823, 1997.
[Non-Patent Document 4] R. Ulichney “The void-and-cluster method for dither array generation,” Proc. SPIE. Vol. 1913, pp. 332-343, 1993.
[Non-Patent Document 5] M. Noar, A. Shamir, “Visual Cryptography,” Proc. Eurocrypt '94, pp. 1-12, 1994
[Non-Patent Document 6] Z. Zhou, G. R. Arce, G. D. Crescenzo, “Halftone Visual Cryptography”, Proc. IEEE Int. Conf. on Image Processing, 2003, Vol. 1, pp. 521-524, 2003.
[Non-Patent Document 7] M. S. Fu, O. C. Au, “A Set of Mutually Watermarked Halftone Images”, IEEE Int. Conf. on Image Processing 2003, Vol. 2, pp. 467-470, 2003.
However, in the tally image generating method using the error diffusion method of the Non-Patent Document 1, a weighting filter is applied to each pixel and errors are weighted and summed up, so that the amount of calculation is large and high-speed generation of tally images is not possible.
Also, in the tally image generating method using the GA method of Non-Patent Document 2, tally images are generated so that density values calculated by applying a Gaussian filter to a binary image come close to input gray-scale pixel values, so that the amount of calculation is large, and high-speed generation of tally images is not possible.
In the tally image generating method using the systematic ordered dither of the Non-Patent Document 3, visually unfavorable regular patterns unique to matrices appear in tally images. In addition, image deterioration is caused due to random matrix switching, and the resolution of a confidential image lowers as the matrix size increases.
In the tally image generating method using the density pattern method of the Patent Document 1, the tally images become dxd times as large as the input image size, and pixels in a cell are randomly determined, whereby the image quality is low.
As described above, the conventional tally image generating methods have problems in that the methods that realize high quality of tallies are long in tally generating time, and the methods that shorten the tally generating time are inferior in image quality and cannot realize high quality and high speed generation of tally images. Herein, the tally generating time means the period until tally images are outputted since a halftone image is inputted.
Tally image generating method using threshold matrices can realize grouping function. At first, Matrix1, Matrix2, , , , Matrix X are generated. Then, Group1, Group2, , , , Group X are generated from each Matrix1, Matrix2, , , , Matrix X, respectively. Each group has a lot of tally images generated from a lot of various input gray-scale images. In decoding step, instructed number groups are selected. Any combination of a selected tally image from each selected Group can decode the confidential image. This grouping function has not been realized conventional halftone tally image generation methods such as Non-Patent Document 1 and 2. This function can be realized by Non-Patent Document 3 but no one propose this grouping usage. This grouping function can be easily realized by tally image generation method using threshold matrices.
Moreover, not only normal (2,2) method but also other method such as (k,n) method can be realized. In Non-Patent Document 5 of (k, n) scheme, overlapping any k share images decode the confidential image, but overlapping less than k−1 random share images can not decode the confidential image. Here, in conventional image, n is not the number of tally images, n is the number of groups. At first, n groups are generated. Then, more than k groups are randomly selected. Any combination of a selected tally image from each selected group can decode the confidential image. Some Halftone tally image generation method can support methods except (2,2) scheme. For example, Non-Patent Document 6 supports (k,n) scheme. Non-Patent Document 6 also supports general access structure, so access feasibility is very high. Non-Patent Document 7 supports (2, 3) scheme. However, Non-Patent Document 6 and 7 do not use threshold matrices, grouping of a lot of high quality tally images described above can not be realized.